package datastructure.hashTable;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 11:00 上午
 */
public class LinearProbingHashST<Key, Value> {
    private Key[] keys;
    private Value[] values;

    private int M;
    private int N;


    public LinearProbingHashST(int m) {
        M = m;
        keys = (Key[]) new Comparable[m];
        values = (Value[]) new Comparable[m];
    }

    public void put(Key key, Value value) {
        if (key == null) {
            return;
        }
        if (value == null) {
            delete(key);
        }
        if (N > 0 && N >= M / 2) {
            resize(M * 2);
        }
        int hash = hash(key);
        int i;
        for (i = hash; keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                values[i] = value;
                return;
            }
        }
        keys[i] = key;
        values[i] = value;
        N++;

    }

    public Value get(Key key) {
        if (key == null) {
            return null;
        }
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                return values[i];
            }
        }
        return null;
    }

    private void resize(int size) {
        LinearProbingHashST<Key, Value> st = new LinearProbingHashST<>(size);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null) {
                st.put(keys[i], values[i]);
            }
        }
        this.M = st.M;
        this.N = st.N;
        this.keys = st.keys;
        this.values = st.values;
    }

    private void delete(Key key) {
        if (key == null) {
            return;
        }
        int i = hash(key);
        while (!keys[i].equals(key)) {
            i = (i + 1) % M;
        }
        keys[i]=null;
        values[i]=null;

        i=(i+1)%M;
        while (keys[i]!=null){
            Key oldkey=keys[i];
            Value oldValue=values[i];
            keys[i]=null;
            values[i]=null;

            N--;

            put(oldkey,oldValue);
            i=(i+1)%M;
        }
        N--;
        if(N>0 && N<=M/8){
            resize(M/2);
        }
    }


    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public static void main(String[] args) {
        LinearProbingHashST<String, Integer> linearProbingHashST = new LinearProbingHashST<>(8);
        linearProbingHashST.put("S", 0);
        linearProbingHashST.put("E", 1);
        linearProbingHashST.put("A", 2);
        System.out.println("size" + linearProbingHashST.M);
        linearProbingHashST.put("R", 3);
        linearProbingHashST.put("C", 4);
        linearProbingHashST.put("H", 5);
        linearProbingHashST.put("E", 6);
        linearProbingHashST.put("X", 7);
        linearProbingHashST.put("A", 8);
        System.out.println("size" + linearProbingHashST.M);

        linearProbingHashST.put("M", 9);
        linearProbingHashST.put("P", 10);
        linearProbingHashST.put("L", 11);
        linearProbingHashST.put("E", 12);
        System.out.println("size" + linearProbingHashST.M);


        System.out.println(linearProbingHashST.get("E"));
        System.out.println(linearProbingHashST.get("P"));

        linearProbingHashST.delete("E");
        linearProbingHashST.delete("M");
        linearProbingHashST.delete("A");
        linearProbingHashST.delete("X");
        linearProbingHashST.delete("L");
        linearProbingHashST.delete("R");
        linearProbingHashST.delete("C");
        linearProbingHashST.delete("S");
        System.out.println(linearProbingHashST.M);
        System.out.println(linearProbingHashST.get("E"));
        System.out.println(linearProbingHashST.get("M"));
        System.out.println(linearProbingHashST.get("L"));

    }
}
